#include "Grafo.h"
//#define DEBUG_MODE YES

Grafo::Grafo(unsigned _cantidadDeVertices, unsigned _cantidadDeAristas): cantidadDeVertices(_cantidadDeVertices),
																		cantidadDeAristas(_cantidadDeAristas){
	vertices = new std::vector <NodoGrafo*> ();
	etiquetas = new std::vector <unsigned> (cantidadDeVertices);
	etiquetaActual = 0;
	cantidadDeVerticesEtiquetados = 0;

	for (unsigned index = 0; index < cantidadDeVertices; ++index) {
		etiquetas->at(index) = 0;
	}
}

Grafo::~Grafo() {
	NodoGrafo* nodo;
	for (unsigned vertice = 0; vertice < vertices->size(); ++vertice) {
		nodo = vertices->at(vertice);
		delete (nodo);
	}
	delete (vertices);
	delete(etiquetas);
}

bool Grafo::visitar(NodoGrafo* nodoActual) {
	std::vector <AristaGrafo*> *adyacencias = nodoActual->getAdyacencias();
	NodoGrafo* nodoAdyacente;
	nodoActual->setFueVisitado(true);
	nodosVisitados.push_back(nodoActual);
	bool directa = false;
	for (unsigned int i = 0; i < adyacencias->size(); i++) {
		nodoAdyacente = nodoActual->getNodoParaAdyacencia(i);
		directa = nodoActual->getRelacionEsDirecta(i);

		if (directa) {
			if (!nodoAdyacente->getFueVisitado()) {
				this->visitar(nodoAdyacente);
			}
			else {
				this->elGrafoEsCiclico = true;
				return true;
			}
		}
	}
	return elGrafoEsCiclico;
}

bool Grafo::esCiclico() {
	std::vector<NodoGrafo*> nodosVisitados;
	std::vector<NodoGrafo*>::iterator itV;
	NodoGrafo* nodoActual;
	this->elGrafoEsCiclico = false;
	bool esCiclico = false;

	for(itV = vertices->begin(); itV != vertices->end() ;++itV) {
		resetNodosVisitados();
		nodoActual = (*itV);
		if (!nodoActual->getFueVisitado()) {
			resetNodosVisitados();
			esCiclico = this->visitar(nodoActual);
			if (esCiclico) {
				this->elGrafoEsCiclico = true;
				resetNodosVisitados();
				return true;
			}
		}
	}
	return this->elGrafoEsCiclico;
}

void Grafo::dirigirNodo(unsigned verticeOrigen, unsigned verticeDestino) {
	NodoGrafo* nodoActual = vertices->at(verticeOrigen);
	NodoGrafo* nodoAdyacente = vertices->at(verticeDestino);
	nodoActual->agregarAdyacencia(nodoAdyacente, etiquetaActual, true);
	nodoAdyacente->agregarAdyacencia(nodoActual, etiquetaActual, false);
	etiquetaActual ++;
}



void Grafo::crearVertices (){
	for (unsigned numeroDeVertice = 0; numeroDeVertice < cantidadDeVertices; ++numeroDeVertice) {
		NodoGrafo *nodo = new NodoGrafo(numeroDeVertice);
		vertices->push_back(nodo);
	}

}
void Grafo::etiquetarUnCamino(std::vector <NodoGrafo*> *verticesAEtiquetar) {
	NodoGrafo *nodoActualUno;
	NodoGrafo *nodoActualDos;

	if (verticesAEtiquetar->size() < 2) {
		return;
	}

	for (unsigned vertice = 0; vertice < verticesAEtiquetar->size() - 1; ++vertice) {
		nodoActualUno = verticesAEtiquetar->at(vertice);
		nodoActualDos = verticesAEtiquetar->at(vertice + 1);
		etiquetarPar(nodoActualUno, nodoActualDos);

	}
}

void Grafo::etiquetarPar(NodoGrafo* nodoUno, NodoGrafo* nodoDos ) {

	NodoGrafo* nodoAuxUno = nodoUno;
	NodoGrafo* nodoAuxDos = nodoDos;
	if (nodoUno->getFueEtiquetado() && nodoDos->getFueEtiquetado()) {
		return;
	}

	else if (!nodoUno->getFueEtiquetado() && nodoDos->getFueEtiquetado()){
		nodoAuxUno = nodoDos;
		nodoAuxDos = nodoUno;
	}

	if (!nodoAuxUno->getFueEtiquetado()) {
		nodoAuxUno->setEtiqueta(0);
		nodoAuxUno->setFueEtiquetado(true);
		cantidadDeVerticesEtiquetados ++;
		cantidadDeVerticesEtiquetados ++;

		etiquetas->at(nodoAuxUno->getNumeroDeVertice()) = 0;
		#ifdef DEBUG_MODE
		std::cout << "ETIQUETO AL NODO: " << nodoAuxUno->getNumeroDeVertice() << " con etiqueta "<< 0 << std::endl;
		#endif
	}
	if (!nodoAuxDos->getFueEtiquetado()) {

		bool etiqueto = nodoAuxUno->setEtiquetaParaAdyacencia(nodoAuxDos->getNumeroDeVertice(), cantidadDeAristas);
		if (etiqueto) {
			nodoAuxDos->setFueEtiquetado(true);
			cantidadDeVerticesEtiquetados ++;
		}
		etiquetas->at(nodoAuxDos->getNumeroDeVertice()) = nodoAuxDos->getEtiqueta();
	}
}

bool Grafo::quedanAdyacenciasSinRecorrer(NodoGrafo* nodoActual) {
	if (!nodoActual) {
		return false;
	}
	std::vector<AristaGrafo*> *adyacencias = nodoActual->getAdyacencias();
	NodoGrafo* nodoAdyacente;
	for (unsigned index = 0; index < adyacencias->size(); index ++) {
		nodoAdyacente = nodoActual->getNodoParaAdyacencia(index);
		if	(!nodoAdyacente->getFueVisitado()) {
			return true;
		}
	}
	return false;
}

bool Grafo::quedanVerticesSinEtiquetar() {
	return (cantidadDeVertices != cantidadDeVerticesEtiquetados);
}

void imprimirVectores (std::vector<NodoGrafo*> * verticesAux, std::vector<NodoGrafo*> * verticesAEtiquetar) {

	std::cout << "Stack aux : ";

	for (unsigned int i = 0; i < verticesAux->size(); ++i) {
		std::cout <<verticesAux->at(i)->getNumeroDeVertice();
	}
	std::cout << std::endl ;
	std::cout << "verticesAEtiquetar:" ;
	for (unsigned int i = 0; i < verticesAEtiquetar->size(); ++i) {
		std::cout <<verticesAEtiquetar->at(i)->getNumeroDeVertice();
	}
	std::flush(std::cout);
	std::cout << std::endl ;
}
bool Grafo::etiquetar() {
	std::vector <NodoGrafo*> *verticesAux = new std::vector<NodoGrafo*>;
	std::vector <NodoGrafo*> *verticesAEtiquetar = new std::vector<NodoGrafo*>;
	std::vector <NodoGrafo*> *verticesPendientes = new std::vector<NodoGrafo*>;
	std::vector <AristaGrafo*> *adyacencias = NULL;
	NodoGrafo* nodoActual;
	NodoGrafo* adyacente;
	bool quedanNodosSinEtiquetar = true;

	for (unsigned vertice = 0; vertice < vertices->size(); ++vertice) {
		nodoActual = vertices->at(vertice);
		adyacencias = nodoActual->getAdyacencias();


		if (adyacencias->size() == 0) {
			nodoActual->setFueVisitado(true);
			nodosVisitados.push_back(nodoActual);
			nodoActual->setFueEtiquetado(true);
			cantidadDeVerticesEtiquetados ++;
		}

		else if (!nodoActual->getFueEtiquetado()) {

			while (quedanNodosSinEtiquetar && nodoActual != NULL) {
				#if defined(DEBUG_MODE)
				std::cout << "APILO EN AUX: " << nodoActual->getNumeroDeVertice() << std::endl;
				#endif
				verticesAux->push_back(nodoActual);



				while (quedanAdyacenciasSinRecorrer(nodoActual)) {

					nodoActual = verticesAux->back();
					nodoActual->setFueVisitado(true);
					verticesAux->pop_back();

					adyacencias = nodoActual->getAdyacencias();
					verticesAEtiquetar->push_back(nodoActual);

					#if defined(DEBUG_MODE)
					std::cout << "DESAPILO EN AUX: " << nodoActual->getNumeroDeVertice() << std::endl;
					std::cout << "APILO EN ETIQUETAS: " << nodoActual->getNumeroDeVertice() << std::endl;
					#endif


					for (unsigned adyacencia = 0; adyacencia < adyacencias->size(); ++adyacencia) {
						adyacente = nodoActual->getNodoParaAdyacencia(adyacencia);
						#if defined(DEBUG_MODE)
						std::cout << "ADYACENTE: " << adyacente->getNumeroDeVertice() << " PARA VERTICE " << nodoActual->getNumeroDeVertice() << std::endl;
						#endif
						if(!nodoActual->adyacenciaVisitada(adyacencia) && !nodoActual->adyacenciaEtiquetada(adyacencia) ){
							adyacente->setFueVisitado(true);
							nodosVisitados.push_back(adyacente);
							#if defined(DEBUG_MODE)
							std::cout << "APILO EN AUX: " << nodoActual->getNodoParaAdyacencia(adyacencia)->getNumeroDeVertice() << std::endl;
							#endif
							verticesAux->push_back(adyacente);

						}

					}
					#if defined(DEBUG_MODE)
					std::cout << "bACK: " << verticesAux->back()->getNumeroDeVertice() << std::endl;
					#endif
					if (verticesAux->size() > 0) {
						nodoActual = verticesAux->back();
					}
					else {
						nodoActual = NULL;
					}


				}

				#if defined(DEBUG_MODE)
				std::cout << "cantidad de vertice aux : " << verticesAux->size() << std::endl;
				#endif

				if (verticesAux->size() > 0) {
					nodoActual = verticesAux->back();
					verticesAux->pop_back();
					adyacencias = nodoActual->getAdyacencias();
					verticesAEtiquetar->push_back(nodoActual);

				}
				else {
					nodoActual = NULL;
				}
				#if defined(DEBUG_MODE)
				imprimirVectores(verticesAux, verticesAEtiquetar);
				#endif

				this->etiquetarUnCamino(verticesAEtiquetar);
				if (verticesAEtiquetar->size() > 0) {
					agregarNodosConAdyacenciasSinEtiquetar(verticesAEtiquetar, verticesPendientes);
				}

				if (verticesPendientes->size() > 0) {
					nodoActual = verticesPendientes->back();
					verticesPendientes->pop_back();
				}
				else {
					nodoActual = NULL;
				}

				resetNodosVisitados();

				quedanNodosSinEtiquetar =  quedanVerticesSinEtiquetar();

				verticesAEtiquetar->clear();
				verticesAux->clear();
			}
		}
	}
	delete (verticesAEtiquetar);
	delete (verticesAux);
	delete (verticesPendientes);
	for (unsigned var = 0; var < cantidadDeVertices; ++var) {
		if (!vertices->at(0)->getFueEtiquetado()) {
			std::cout << "NO FUE" << std::endl;
		}

	}
	return true;
}

void Grafo::agregarNodosConAdyacenciasSinEtiquetar(std::vector<NodoGrafo*> * verticesAEtiquetar, std::vector<NodoGrafo*> * verticesPendientes) {
	std::vector <AristaGrafo*> *adyacencias;
	NodoGrafo* nodoVertice = NULL;
	NodoGrafo* nodoAdy = NULL;
	for (unsigned vertice = 0; vertice < verticesAEtiquetar->size(); ++vertice) {
		nodoVertice = verticesAEtiquetar->at(vertice);
		adyacencias = nodoVertice->getAdyacencias();
		for (unsigned adyacencia = 0; adyacencia < adyacencias->size(); ++adyacencia) {
			nodoAdy = nodoVertice->getNodoParaAdyacencia(adyacencia);
			if (!nodoAdy->getFueEtiquetado()){
				verticesPendientes->push_back(nodoVertice);
			}
		}
	}
}
NodoGrafo* Grafo::siguienteNodoConAdyacenciasSinEtiquetar(std::vector<NodoGrafo*> * verticesAEtiquetar) {

	std::vector <AristaGrafo*> *adyacencias;
	NodoGrafo* nodoVertice = NULL;
	NodoGrafo* nodoAdy = NULL;
	for (unsigned vertice = 0; vertice < verticesAEtiquetar->size(); ++vertice) {
		nodoVertice = verticesAEtiquetar->at(vertice);
		adyacencias = nodoVertice->getAdyacencias();
		for (unsigned adyacencia = 0; adyacencia < adyacencias->size(); ++adyacencia) {
			nodoAdy = nodoVertice->getNodoParaAdyacencia(adyacencia);
			if (!nodoAdy->getFueEtiquetado()){
				return nodoVertice;
			}
		}
	}
	return NULL;
}
void Grafo::imprimirFuncionG() {
	std::cout << "Tabla G"  << std::endl;
	for (unsigned int i = 0; i < cantidadDeVertices; ++i) {
		std::cout << "Nodo numero: " << i << " G(x): " << etiquetas->at(i) << std::endl;
	}
}

std::vector<unsigned > *Grafo::getEtiquetas() const {
    return etiquetas;
}

void Grafo::setEtiquetasParaVertice(unsigned vertice, unsigned valor) {
    this->etiquetas->at(vertice) = valor;
}

unsigned Grafo::getEtiquetaVertice (unsigned numeroVertice) {
	return etiquetas->at(numeroVertice);
}

void Grafo::resetNodosVisitados() {
	std::vector<NodoGrafo*>::iterator it;
	NodoGrafo* nodoActual;
	for (it = nodosVisitados.begin(); it != nodosVisitados.end(); ++it) {
		nodoActual = (*it);
		nodoActual->setFueVisitado(false);
	}
	nodosVisitados.clear();
}

 NodoGrafo* Grafo::getNodoVertice(unsigned numeroDeVertice) const {
	 return vertices->at(numeroDeVertice);
 }
